package main.面试金典第六版;

import java.util.*;

public class Interview17 {
    public static void main(String[] args) {
        System.out.println("面试题17.01：不用加号的加法");
        System.out.println("面试题17.04：消失的数字");
        System.out.println("面试题17.05：字母与数字");
        System.out.println("面试题17.06：2出现的次数");
        System.out.println("面试题17.07：婴儿名字");
        System.out.println("面试题17.08：马戏团人塔");
        System.out.println("面试题17.09：第K个数");
        System.out.println("面试题17.10：主要元素");
        System.out.println("面试题17.11：单词距离");
        System.out.println("面试题17.12：BiNode");
        System.out.println("面试题17.13：恢复空格");
        System.out.println("面试题17.14：最小K个数");
        System.out.println("面试题17.15：最长单词");
        System.out.println("面试题17.16：按摩师");
        System.out.println("面试题17.17：多次搜索");
        System.out.println("面试题17.18：最短超串");
        System.out.println("面试题17.19：消失的两个数字");
        System.out.println("面试题17.20：连续中值");
        System.out.println("面试题17.21：直方图的水量");
        System.out.println("面试题17.22：单词转换");
        System.out.println("面试题17.23：最大黑方阵");
        System.out.println("面试题17.24：最大子矩阵");
        System.out.println("面试题17.25：单词矩阵");
        System.out.println("面试题17.26：稀疏相似度");
    }
}

class Interview_17_01{
    public int add(int a, int b) {
        return Math.addExact(a,b);
    }
}

class Interview_17_04{
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int result=nums.length;
        for (int i=0;i<nums.length;i++) {
            if (i!=nums[i]) {
                result=i;
                break;
            }
        }
        return result;
    }
}

class Interview_17_05{
    public String[] findLongestSubarray(String[] array) {
        return null;
    }
}

class Interview_17_09{
    public int getKthMagicNumber(int k) {
        int[] dp=new int[k];
        int p3=0,p5=0,p7=0;
        dp[0]=1;
        for (int i=1;i<k;i++) {
            dp[i]=Math.min(3*dp[p3],Math.min(5*dp[p5],7*dp[p7]));
            if (3*dp[p3]==dp[i]) p3++;
            if (5*dp[p5]==dp[i]) p5++;
            if (7*dp[p7]==dp[i]) p7++;
        }
        return dp[k-1];
    }
}

class Interview_17_10{
    public int majorityElement(int[] nums) {
        if (nums.length==1) return nums[0];
        Arrays.sort(nums);
        int left=0,right=0,result=-1;
        while (right< nums.length) {
            if (nums[left]!=nums[right]) {
                left=right;
            }
            if (nums[left]==nums[right]) {
                if (right-left+1> nums.length/2) {
                    result=nums[left];
                }
            }
            right++;
        }
        return result;
    }
}

class Interview_17_11{
    public int findClosest(String[] words, String word1, String word2) {
        int left=-1,right=-1,min=Integer.MAX_VALUE;
        for (int i=0;i<words.length&&min>1;i++) {
            if (words[i].equals(word1)) {
                left=i;
                if (right!=-1) min=Math.min(min,left-right);
            }else if (words[i].equals(word2)) {
                right=i;
                if (left!=-1) min=Math.min(min,right-left);
            }
        }
        return min;
    }
}

class Interview_17_12{
    TreeNode head = new TreeNode(-1);   // 为了返回单向链表的头节点而多设的一个节点
    TreeNode perv = null;               // 指向当前节点的前一个节点
    public TreeNode convertBiNode(TreeNode root) {
        process(root);
        return head.right;
    }
    public void process(TreeNode root) {
        if (root == null) { return;}
        process(root.left);
        if (perv == null) {     // 第一个节点
            perv = root;        // 记录第一个节点
            head.right = root;  // 记录它，它将作为单链表的表头
        } else {                // 第一个节点之后的节点
            perv.right = root;  // 前一个节点的右指针指向当前节点
            perv = root;        // 更新perv指向
        }
        root.left = null;       // 当前节点的左指针设为null
        process(root.right);
    }
}

class Interview_17_14{
    public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] result=new int[k];
        for (int i=0;i<k;i++) result[i]=arr[i];
        return result;
    }
}

class Interview_17_16{
    public int massage(int[] nums) {
        if (nums.length==0) return 0;
        if (nums.length==1) return nums[0];
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        dp[1]=nums[1];
        int preMax=dp[0];
        for (int i=2;i< nums.length;i++) {
            dp[i]=nums[i]+preMax;
            preMax=Math.max(preMax,dp[i-1]);
        }
        return dp[nums.length-1] > dp[nums.length-2] ? dp[nums.length-1] : dp[nums.length-2];
    }
}

class Interview_17_18{
    public int[] shortestSeq(int[] big, int[] small) {
        int minLength = big.length + 1;
        int[] count = new int[small.length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < small.length; i ++) map.put(small[i], i);
        int left = 0, right = 0;
        int find = 0;
        int[] res = new int[2];
        while (right < big.length) {// 扩展右边界
            int rightNum = big[right];
            if (map.containsKey(rightNum)) {
                count[map.get(rightNum)] ++;
                if (count[map.get(rightNum)] == 1) find ++;
            }
            while (find == small.length) {// 缩小左边界
                if (right - left + 1 < minLength) {
                    res[0] = left;
                    res[1] = right;
                    minLength = right - left + 1;
                }
                int leftNum = big[left];
                if (map.containsKey(leftNum)) {
                    count[map.get(leftNum)] --;
                    if (count[map.get(leftNum)] == 0) find --;
                }
                left ++;
            }
            right ++;
        }
        return minLength <= big.length ? res : new int[0];
    }
}

class Interview_17_19{
    public int[] missingTwo(int[] nums) {
        int[] arr=new int[nums.length+3];
        for (int i=0;i<nums.length;i++) arr[nums[i]]=nums[i];
        int[] result=new int[2];
        for (int i=0,j=1;j< arr.length&&i!=2;j++) {
            if (arr[j]==0) result[i++]=j;
        }
        return result;
    }
}

class Interview_17_20{
    PriorityQueue<Integer> queMin,queMax;

    public Interview_17_20() {
        queMin = new PriorityQueue<Integer>((a, b) -> (b - a));//降序小于中位数的数
        queMax = new PriorityQueue<Integer>((a, b) -> (a - b));//升序大于中位数的数
    }

    public void addNum(int num) {
        if (queMin.isEmpty() || num <= queMin.peek()) {
            queMin.offer(num);
            if (queMax.size() + 1 < queMin.size()) queMax.offer(queMin.poll());
        } else {
            queMax.offer(num);
            if (queMax.size() > queMin.size()) {
                queMin.offer(queMax.poll());
            }
        }
    }

    public double findMedian() {
        if (queMin.size() > queMax.size()) return queMin.peek();
        return (queMin.peek() + queMax.peek()) / 2.0;
    }
}

class Interview_17_21{
    public int trap(int[] height) {
        if (height.length==0) return 0;
        int result=0,length= height.length;
        int[] leftHeight=new int[length],rightHeight=new int[length];
        int temp=height[0];
        for (int i=0;i<length;i++){//i位置左侧最高值
            if (i==0) leftHeight[i]=0;
            else {
                if (temp>height[i]) leftHeight[i]=temp;
                else {
                    temp=height[i];
                    leftHeight[i]=0;
                }
            }
        }
        temp=height[length-1];
        for (int i=length-1;i>=0;i--){//i位置右侧最高值
            if (i==length-1) rightHeight[i]=0;
            else {
                if (temp>height[i]) rightHeight[i]=temp;
                else {
                    temp=height[i];
                    rightHeight[i]=0;
                }
            }
        }
        for (int i=0;i<length;i++){
            int min=Math.min(leftHeight[i],rightHeight[i]);
            if (min>height[i]){//两侧高度大于当前高度，则能接雨水
                result+=min-height[i];
            }
        }
        return result;
    }
}

class Interview_17_22{
    public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (!wordList.contains(endWord)) return new ArrayList<>();
        return process1(beginWord, endWord, wordList, new HashSet<>());
    }
    public LinkedList<String> process1(String beginWord, String endWord, List<String> wordList, Set<String> visited) {
        if (beginWord.equals(endWord)) {
            LinkedList<String> collector = new LinkedList<>();
            collector.addFirst(beginWord);
            return collector;
        }
        visited.add(beginWord);
        for (String s : wordList) {
            if (visited.contains(s)) continue;
            if (process2(beginWord, s)) {
                LinkedList<String> sub = process1(s, endWord, wordList, visited);
                if (!sub.isEmpty()) {
                    sub.addFirst(beginWord);
                    return sub;
                }
            }
        }
        return new LinkedList<>();
    }
    public boolean process2(String w1, String w2) {
        if (w1.length() != w2.length()) return false;
        int n = w1.length();
        int diff = 0;
        for (int i = 0; i < n; i++) {
            if (w1.charAt(i) != w2.charAt(i) && ++diff > 1) return false;
        }
        return true;
    }
}

class Interview_17_25{
    public String[] maxRectangle(String[] words) {
        Map<Integer,List<String>> map=new HashMap<>();
        return null;
    }
}